package com.ryujung.dp.leetCode_84;

import java.util.ArrayDeque;
import java.util.Deque;

/*
 * @lc app=leetcode.cn id=84 lang=java
 *
 * [84] 柱状图中最大的矩形
 *
 * https://leetcode-cn.com/problems/largest-rectangle-in-histogram/description/
 *
 * algorithms
 * Hard (39.32%)
 * Likes:    567
 * Dislikes: 0
 * Total Accepted:    43.9K
 * Total Submissions: 111.5K
 * Testcase Example:  '[2,1,5,6,2,3]'
 *
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * 
 * 
 * 
 * 
 * 
 * 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
 * 
 * 
 * 
 * 
 * 
 * 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
 * 
 * 
 * 
 * 示例:
 * 
 * 输入: [2,1,5,6,2,3]
 * 输出: 10
 * 
 */

// @lc code=start
class Solution {
    /**
     * 暴力解法,测试超时 设置三个指针,第一个指针i,从0~heights.length-1遍历,代表长方形的宽左侧角标 第二个指针j,
     * 从i~heights.length,代表在i~j范围内寻找最大的长方形 第三个指针k,从i~j之间寻找到最小的高度minHeight, 用最小高度 *
     * k当前的宽度,并用变量maxArea记录即可
     * 
     * 列出所有可以组成的长方形的面积 Time: O(n^3) Space:O(1)
     */
    public int largestRectangleArea1(int[] heights) {
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            for (int j = i; j < heights.length; j++) {
                int minHeight = Integer.MAX_VALUE;
                for (int k = i; k <= j; k++) {
                    minHeight = Math.min(minHeight, heights[k]);
                    maxArea = Math.max(maxArea, minHeight * (k - i + 1));
                }
            }
        }
        return maxArea;
    }

    /**
     * 暴力解法的优化 将上述方案中的三个指针变为两个指针 Time: O(n^2) Space:O(1)
     */
    public int largestRectangleArea2(int[] heights) {
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            // 左索引移动后要将minHeight清零
            int minHeight = Integer.MAX_VALUE;

            for (int j = i; j < heights.length; j++) {
                minHeight = Math.min(minHeight, heights[j]);
                maxArea = Math.max(maxArea, minHeight * (j - i + 1));
            }
        }
        return maxArea;
    }

    /**
     * 栈 思路: 当柱状图的下一个高度低于当前直方图的高度就可以确定当前柱状图的最大面积
     * 当柱状图的下一个高度大于等于当前的柱状图的高度,并不能确定当前柱状图的高度, 使用栈的数据结构将不能确定最大面积的柱状图所在的索引记录下来,
     * 直到找到一个柱高度低于前一个柱高度的索引,从而依次计算栈内的所有没有确定最大面积的元素
     * 
     * 计算方式为: 定义返回的最大面积,记录遍历过程中出现的最大面积值maxArea; 首先记录低于前一个柱高度的那个柱对应的索引small;
     * 最大面积的高:获取栈顶存储的索引index,找到对应的高度heights[index]; 最大面积的宽: maxArea = max( (small -
     * index)*heights[index], maxArea )
     * 
     * 每计算一个索引,就让一个索引出栈,直到索引全部被取出,即可返回maxArea
     */
    public static int largestRectangleArea3(int[] heights) {
        if (heights == null || heights.length == 0)
            return 0;

        Deque<Integer> stack = new ArrayDeque<>();
        int maxArea = 0;

        int length = heights.length;
        for (int i = 1; i <= length; i++) {
            int h = i == length ? -1 : heights[i];

            if (h < heights[i - 1]) {
                while (!stack.isEmpty()) {
                    int index = stack.pop();
                    int height = heights[index];
                    maxArea = Math.max(maxArea, height * (i - index));
                }
            }
            stack.push(i);
        }
        return maxArea;

    }

    public static void main(String[] args) {
        // int[] heights = { 2, 1, 5, 6, 2, 3 };
        int[] heights = { 6, 7, 5, 2, 4, 5, 9, 3 };
        // int[] heights = { 1 };
        // int[] heights = { 1, 2, 1 };
        // int[] heights = { 1, 1 };
        // System.out.println(s.largestRectangleArea(heights));
        System.out.println(largestRectangleArea(heights));
    }

    /**
     * 2021年12月25日 发现作过的题已经忘了，解法也不记得，故重做。
     */
    public static int largestRectangleArea4(int[] heights) {
        int maxArea = 0, minHeight = 0;
        for (int i = 0; i < heights.length; i++) {
            minHeight = heights[i];
            for (int j = i; j < heights.length; j++) {
                minHeight = Math.min(minHeight, heights[j]);
                maxArea = Math.max(maxArea, minHeight * (j - i + 1));
            }
        }
        return maxArea;
    }

    /**
     * 栈思想： 如果要计算包含当前直方图的最大面积，那么当出现height大于当前时，不计算面积，直接跳过 直到出现height小于当前的列，或者遍历到边界。
     * 
     * 用数组记录下每个index对应的最长宽度，遍历计算取最大值即可
     * 
     */
    public static int largestRectangleArea5(int[] heights) {
        int maxArea = 0;
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int len = heights.length;
        int[] left = new int[len];
        int[] right = new int[len];
        for (int i = 0; i < heights.length; i++) {
            int h = heights[i];
            while (!stack.isEmpty() && heights[stack.peek()] > h) {
                right[stack.pop()] = i;
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        stack.forEach(i -> right[i] = len);
        for (int i = 0; i < right.length; i++) {
            maxArea = Math.max(maxArea, heights[i] * (right[i] - left[i] - 1));
        }
        return maxArea;
    }

    // 栈方式优化
    public static int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int len = heights.length;
        int[] left = new int[len + 1];
        for (int i = 0; i <= heights.length; i++) {
            int h = i == heights.length ? -1 : heights[i];
            while (!stack.isEmpty() && heights[stack.peek()] > h) {
                int idx = stack.pop();
                maxArea = Math.max(maxArea, heights[idx] * (i - left[idx] - 1));
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        return maxArea;
    }

}
// @lc code=end
